package _0844_Backspace_String_Compare;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Date: 2020/10/19 9:08
 * Content: 栈
 */
public class Solution {

    private String get(String s) {

        Deque<Character> stk = new ArrayDeque<>();
        for (char c : s.toCharArray())
            if (c != '#') stk.push(c);
            else if (!stk.isEmpty()) stk.pop();

        StringBuilder sb = new StringBuilder();
        while (!stk.isEmpty()) sb.append(stk.pop());

        return sb.reverse().toString();
    }

    public boolean backspaceCompare(String S, String T) {
        return get(S).equals(get(T));
    }

    public static void main(String[] args) {

        System.out.println((new Solution()).backspaceCompare("ab#c", "ad#c"));  // true
        System.out.println((new Solution()).backspaceCompare("ab##", "c#d#"));  // true
        System.out.println((new Solution()).backspaceCompare("a##c", "#a#c"));  // true
        System.out.println((new Solution()).backspaceCompare("a#c", "b"));  // false
    }
}
